package com.tree.leetcode.linklist;

import com.tree.leetcode.common.ListNode;

/**
 * @ClassName com.tree.leetcode.linklist
 * Description: <类功能描述>.
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

 * @Author frankzsliu
 * @Date 2024/1/29 16:11
 * @Version 1.0
 */
public class MergeTwoLists_21 {
    public static void main(String[] args) {

    }

    /**
     * 递归
     *
     * 1. 入参： 2个listnode
     * 2. 终止条件
     * 3. 确定单层递归
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null ){
            return list2;
        }
        else if(list2 == null ){
            return list1;
        }
        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }

    /**
     * 迭代
     * @param list1
     * @param list2
     * @return
     */
    public static ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        //前一个节点
        ListNode prev = dummy;

        while (list1!= null && list2 != null){
            if(list1.val < list2.val){
                //链接当前节点
                prev.next = list1;
                //list1节点后移一个
                list1 = list1.next;
            }else {
                prev.next =list2;
                list2 =list2.next;
            }
            //prev前移一位
            prev = prev.next;
        }
        prev.next = list1 ==null? list2:list1;

        return dummy.next;
    }




}
